package com.mj.listen3.链表;

/**
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
 */
public class _83_删除排序链表中的重复元素 {

    /**
     * 不使用额外空间
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p1 = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (p1.val != cur.val) {
                p1.next = cur;
                p1 = p1.next;
            }
            cur = cur.next;
        }
        p1.next = null;
        return head;
    }


    /**
     * 使用一个额外空间
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = new ListNode(head.val);
        ListNode p1 = newHead;
        // 这行代码是个优化。不加的话下面 while 循环中会多判断一次
        head = head.next;
        while (head != null) {
            if (head.val != p1.val) {
                // 遍历到的当前节点与前一个节点不同，则添加到新链表中
                p1.next = head;
                p1 = p1.next;
            }
            head = head.next;
        }
        // 最后尾节点应该为null
        p1.next = null;
        return newHead;
    }
}
